For the demand of high speed and massive connections of next-generation mobile communication, improving the total secondary users' transmission rate by the optimization of power allocation in Cognitive Radio-Non-Orthogonal Multi-Access (CR-NOMA) hybrid system was studied, and an algorithm of Power Allocation based on Tabu Search and Q-learning (PATSQ) was proposed. Firstly, the users' power allocation was observed and learnt by the cognitive base station in the system environment, and the secondary users used NOMA to access the authorized channel. Then, the power allocation, channel state and total transmission rate in the power allocation problem were expressed as action, state and reward in the Markov decision process, which was solved by combining tabu search and Q-learning and an optimal tabu Q-table was obtained. Finally, under the constraints of primary and secondary users' Quality of Service (QoS) and maximum transmitting power, optimal power allocation factors were obtained by the cognitive base station by looking up the tabu Q-table, so as to maximize the total transmission rate of secondary users in the system. Simulation results show that under the same total power, the proposed algorithm is superior to Cognitive Mobile Radio Network (CMRN) algorithm, Secondary user First Decode Mode (SFDM) algorithm and the traditional equal power allocation algorithm in terms of the total transmission rate of secondary users and the number of users contained in the system.